package com.peng.linkedlist;

import java.util.HashMap;
import java.util.Map;

/**
 * 链表（含rand随机指针）复制问题
 */
public class Test04_CopyListWIthRandom {

    public static Node implement01(Node head){
        if(head==null){
            return null;
        }
        Map<Node,Node> map = new HashMap<>();
        Node cur = head;
        while (cur!=null){
            map.put(cur,new Node(cur.value));
            cur =cur.next;
        }

        cur = head;
        while (cur!=null){
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur =cur.next;
        }

        return map.get(head);

    }

    public static Node implement02(Node head){
        if(head==null){
            return null;
        }
        Node cur = head;
        // 把拷贝的节点塞到源节点的后边：
        // 1-1`-2-2`-3-3`
        while (cur!=null){
            Node next = cur.next;
            cur.next = new Node(cur.value);
            cur.next.next = next;
            cur =next;
        }

        cur = head;
        while (cur!=null){
            Node next = cur.next.next;
            cur.next.random = cur.random!=null?cur.random.next:null;
            cur =next;
        }

        //拆离出源节点和copy节点
        cur = head;
        Node res = head.next;
        while (cur!=null){
            Node next = cur.next.next;
            cur.next.next = next!=null?next.next:null;
            cur.next = next;
            cur =next;
        }

        return res;


    }

    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);

        node1.next = node2;
        node1.random = node4;
        node2.next = node3;
        node2.random = node1;
        node3.next = node4;
        node3.random = node1;
        node4.next = node5;
        node4.random = node2;

        Node node = implement01(node1);
//        Node node = implement02(node1);
        System.out.println(node);

    }

    private static class Node{
        private int value;
        private Node next;
        private Node random;

        public Node(int value) {
            this.value = value;
        }
    }
}
